package main

import (
	"container/list"
	"errors"
	"fmt"
	"sync"
	"sync/atomic"
)

// 公共类型定义
type PageID uint64
type FrameID uint64

// 公共错误定义
var (
	ErrNoFreeFrame      = errors.New("no free frame available")
	ErrPageNotInPool    = errors.New("page not in buffer pool")
	ErrSchedulerStopped = errors.New("disk scheduler stopped")
)

// --------------------------- ARC替换器实现 ---------------------------

// ArcReplacer 自适应替换缓存
type ArcReplacer struct {
	mu            sync.Mutex
	mru           *list.List                // 最近访问1次的页列表
	mfu           *list.List                // 最近访问>1次的页列表
	mruGhost      map[PageID]struct{}       // MRU幽灵列表
	mfuGhost      map[PageID]struct{}       // MFU幽灵列表
	pageFrameMap  map[PageID]FrameID        // PageID→FrameID映射
	framePageMap  map[FrameID]PageID        // FrameID→PageID映射
	frameListMap  map[FrameID]*list.Element // FrameID→列表节点映射
	frameListType map[FrameID]*list.List    // FrameID→所属列表类型映射
	mruTargetSize uint64                    // MRU列表目标大小
	currSize      uint64                    // 当前可驱逐帧数量
	capacity      uint64                    // 总容量
}

// NewArcReplacer 创建ARC替换器实例
func NewArcReplacer(capacity uint64) *ArcReplacer {
	return &ArcReplacer{
		mru:           list.New(),
		mfu:           list.New(),
		mruGhost:      make(map[PageID]struct{}),
		mfuGhost:      make(map[PageID]struct{}),
		pageFrameMap:  make(map[PageID]FrameID),
		framePageMap:  make(map[FrameID]PageID),
		frameListMap:  make(map[FrameID]*list.Element),
		frameListType: make(map[FrameID]*list.List),
		mruTargetSize: 0,
		currSize:      0,
		capacity:      capacity,
	}
}

// Size 返回可驱逐帧数量
func (a *ArcReplacer) Size() uint64 {
	a.mu.Lock()
	defer a.mu.Unlock()
	return a.currSize
}

// SetEvictable 标记帧是否可驱逐
func (a *ArcReplacer) SetEvictable(frameID FrameID, pageID PageID, setEvictable bool) {
	a.mu.Lock()
	defer a.mu.Unlock()

	if setEvictable {
		// 帧变为可驱逐
		a.pageFrameMap[pageID] = frameID
		a.framePageMap[frameID] = pageID

		// 检查是否已经在列表中
		if _, exists := a.frameListMap[frameID]; !exists {
			elem := a.mru.PushFront(frameID)
			a.frameListMap[frameID] = elem
			a.frameListType[frameID] = a.mru
			a.currSize++
			a.evictGhostIfNeeded()
		}
	} else {
		// 帧变为不可驱逐
		a.removeFromAllLists(frameID)
		delete(a.pageFrameMap, pageID)
		delete(a.framePageMap, frameID)
		delete(a.frameListMap, frameID)
		delete(a.frameListType, frameID)
		if a.currSize > 0 {
			a.currSize--
		}
	}
}

// RecordAccess 记录页访问
func (a *ArcReplacer) RecordAccess(frameID FrameID, pageID PageID) {
	a.mu.Lock()
	defer a.mu.Unlock()

	// 检查是否在MRU列表
	if elem, ok := a.frameListMap[frameID]; ok && a.frameListType[frameID] == a.mru {
		a.mru.Remove(elem)
		newElem := a.mfu.PushFront(frameID)
		a.frameListMap[frameID] = newElem
		a.frameListType[frameID] = a.mfu
		return
	}

	// 检查是否在MFU列表
	if elem, ok := a.frameListMap[frameID]; ok && a.frameListType[frameID] == a.mfu {
		a.mfu.MoveToFront(elem)
		return
	}

	// 检查是否在MRU幽灵列表
	if _, ok := a.mruGhost[pageID]; ok {
		a.adjustMRUTarget(true)
		delete(a.mruGhost, pageID)
		a.removeFromAllLists(frameID)
		elem := a.mfu.PushFront(frameID)
		a.frameListMap[frameID] = elem
		a.frameListType[frameID] = a.mfu
		a.currSize++ // 添加到列表，增加可驱逐计数
		return
	}

	// 检查是否在MFU幽灵列表
	if _, ok := a.mfuGhost[pageID]; ok {
		a.adjustMRUTarget(false)
		delete(a.mfuGhost, pageID)
		a.removeFromAllLists(frameID)
		elem := a.mfu.PushFront(frameID)
		a.frameListMap[frameID] = elem
		a.frameListType[frameID] = a.mfu
		a.currSize++ // 添加到列表，增加可驱逐计数
		return
	}

	// 不在任何列表，加入MRU头部
	a.removeFromAllLists(frameID)
	elem := a.mru.PushFront(frameID)
	a.frameListMap[frameID] = elem
	a.frameListType[frameID] = a.mru
	a.currSize++ // 添加到列表，增加可驱逐计数
	a.evictGhostIfNeeded()
}

// Evict 驱逐一个可驱逐帧
func (a *ArcReplacer) Evict() *FrameID {
	a.mu.Lock()
	defer a.mu.Unlock()

	if a.currSize == 0 {
		return nil
	}

	var victimFrameID FrameID
	// 优先驱逐方向
	if uint64(a.mru.Len()) >= a.mruTargetSize {
		// 从MRU尾部驱逐
		if back := a.mru.Back(); back != nil {
			victimFrameID = back.Value.(FrameID)
			a.mru.Remove(back)
			pageID := a.framePageMap[victimFrameID]
			a.mruGhost[pageID] = struct{}{}
		} else {
			// 从MFU尾部驱逐
			back := a.mfu.Back()
			victimFrameID = back.Value.(FrameID)
			a.mfu.Remove(back)
			pageID := a.framePageMap[victimFrameID]
			a.mfuGhost[pageID] = struct{}{}
		}
	} else {
		// 从MFU尾部驱逐
		if back := a.mfu.Back(); back != nil {
			victimFrameID = back.Value.(FrameID)
			a.mfu.Remove(back)
			pageID := a.framePageMap[victimFrameID]
			a.mfuGhost[pageID] = struct{}{}
		} else {
			// 从MRU尾部驱逐
			back := a.mru.Back()
			victimFrameID = back.Value.(FrameID)
			a.mru.Remove(back)
			pageID := a.framePageMap[victimFrameID]
			a.mruGhost[pageID] = struct{}{}
		}
	}

	// 清理映射
	delete(a.frameListMap, victimFrameID)
	delete(a.frameListType, victimFrameID)
	pageID := a.framePageMap[victimFrameID]
	delete(a.pageFrameMap, pageID)
	delete(a.framePageMap, victimFrameID)

	a.currSize--
	return &victimFrameID
}

// Remove 从ARC中移除指定帧
func (a *ArcReplacer) Remove(frameID FrameID) {
	a.mu.Lock()
	defer a.mu.Unlock()

	a.removeFromAllLists(frameID)
	if pageID, ok := a.framePageMap[frameID]; ok {
		delete(a.pageFrameMap, pageID)
		delete(a.framePageMap, frameID)
		delete(a.mruGhost, pageID)
		delete(a.mfuGhost, pageID)
	}
	delete(a.frameListMap, frameID)
	delete(a.frameListType, frameID)

	if a.currSize > 0 {
		a.currSize--
	}
}

// 辅助方法：从所有列表中移除帧
func (a *ArcReplacer) removeFromAllLists(frameID FrameID) {
	elem, ok := a.frameListMap[frameID]
	if !ok {
		return
	}

	listType, listOk := a.frameListType[frameID]
	if listOk {
		listType.Remove(elem)
	}
}

// 辅助方法：调整MRU目标大小
func (a *ArcReplacer) adjustMRUTarget(increase bool) {
	if increase && a.mruTargetSize < a.capacity {
		a.mruTargetSize++
	} else if !increase && a.mruTargetSize > 0 {
		a.mruTargetSize--
	}
}

// 辅助方法：若容量超限，驱逐幽灵列表元素
func (a *ArcReplacer) evictGhostIfNeeded() {
	for a.currSize > a.capacity {
		if len(a.mruGhost) > 0 {
			for pid := range a.mruGhost {
				delete(a.mruGhost, pid)
				break
			}
		} else if len(a.mfuGhost) > 0 {
			for pid := range a.mfuGhost {
				delete(a.mfuGhost, pid)
				break
			}
		}
		a.currSize--
	}
}

// --------------------------- 磁盘调度器实现 ---------------------------

// DiskRequest 磁盘I/O请求
type DiskRequest struct {
	IsWrite bool
	PageID  PageID
	Data    []byte
	Done    chan struct{}
}

// DiskManager 磁盘I/O接口
type DiskManager interface {
	ReadPage(pageID PageID, data []byte) error
	WritePage(pageID PageID, data []byte) error
}

// MockDiskManager 模拟磁盘管理器（测试用）
type MockDiskManager struct{}

func (m *MockDiskManager) ReadPage(pageID PageID, data []byte) error {
	// 模拟读操作：用PageID填充数据
	for i := range data {
		data[i] = byte(pageID % 256)
	}
	return nil
}

func (m *MockDiskManager) WritePage(pageID PageID, data []byte) error {
	// 模拟写操作：不做实际写入
	return nil
}

// DiskScheduler 磁盘调度器
type DiskScheduler struct {
	mu            sync.Mutex
	diskManager   DiskManager
	requestQueue  []*DiskRequest
	cond          *sync.Cond
	stopChan      chan struct{}
	workerRunning bool
}

// NewDiskScheduler 创建磁盘调度器
func NewDiskScheduler(diskManager DiskManager) *DiskScheduler {
	ds := &DiskScheduler{
		diskManager:  diskManager,
		requestQueue: make([]*DiskRequest, 0),
		stopChan:     make(chan struct{}),
	}
	ds.cond = sync.NewCond(&ds.mu)
	return ds
}

// Start 启动磁盘调度器
func (d *DiskScheduler) Start() {
	d.mu.Lock()
	defer d.mu.Unlock()
	if d.workerRunning {
		return
	}
	d.workerRunning = true
	go d.workerLoop()
}

// Schedule 添加请求到调度队列
func (d *DiskScheduler) Schedule(req *DiskRequest) error {
	d.mu.Lock()
	defer d.mu.Unlock()

	if !d.workerRunning {
		return ErrSchedulerStopped
	}

	req.Done = make(chan struct{})
	d.requestQueue = append(d.requestQueue, req)
	d.cond.Signal()
	return nil
}

// Stop 停止磁盘调度器
func (d *DiskScheduler) Stop() {
	d.mu.Lock()
	defer d.mu.Unlock()
	if !d.workerRunning {
		return
	}
	close(d.stopChan)
	d.cond.Signal()
	d.workerRunning = false
}

// 工作循环
func (d *DiskScheduler) workerLoop() {
	for {
		select {
		case <-d.stopChan:
			return
		default:
			d.mu.Lock()
			for len(d.requestQueue) == 0 {
				d.cond.Wait()
			}
			// 取出队首请求（FIFO策略）
			req := d.requestQueue[0]
			d.requestQueue = d.requestQueue[1:]
			d.mu.Unlock()

			// 执行I/O操作
			if req.IsWrite {
				_ = d.diskManager.WritePage(req.PageID, req.Data)
			} else {
				_ = d.diskManager.ReadPage(req.PageID, req.Data)
			}

			// 通知完成（忽略错误）
			close(req.Done)
		}
	}
}

// --------------------------- 缓冲池管理器实现 ---------------------------

// FrameHeader 帧元数据
type FrameHeader struct {
	pageID   PageID
	isDirty  bool
	pinCount atomic.Uint32
	data     []byte
}

// ReadPageGuard 读页守卫（RAII）
type ReadPageGuard struct {
	bpm   *BufferPoolManager
	frame *FrameHeader
	mu    sync.Mutex // 确保Close只被调用一次
}

// Data 返回页数据
func (g *ReadPageGuard) Data() []byte {
	return g.frame.data
}

// Close 释放页
func (g *ReadPageGuard) Close() {
	g.mu.Lock()
	defer g.mu.Unlock()

	if g.bpm == nil || g.frame == nil {
		return
	}

	g.bpm.mu.Lock()
	defer g.bpm.mu.Unlock()

	oldPinCount := g.frame.pinCount.Add(^uint32(0)) // 减1
	if oldPinCount == 1 {
		pageID := g.frame.pageID
		frameID := g.bpm.pageTable[pageID]
		g.bpm.arcReplacer.SetEvictable(frameID, pageID, true)
	}

	g.bpm = nil
	g.frame = nil
}

// WritePageGuard 写页守卫（RAII）
type WritePageGuard struct {
	bpm   *BufferPoolManager
	frame *FrameHeader
	mu    sync.Mutex // 确保Close只被调用一次
}

// Data 返回页数据
func (g *WritePageGuard) Data() []byte {
	return g.frame.data
}

// Close 释放页
func (g *WritePageGuard) Close() {
	g.mu.Lock()
	defer g.mu.Unlock()

	if g.bpm == nil || g.frame == nil {
		return
	}

	g.bpm.mu.Lock()
	defer g.bpm.mu.Unlock()

	// 标记为脏页
	g.frame.isDirty = true

	oldPinCount := g.frame.pinCount.Add(^uint32(0)) // 减1
	if oldPinCount == 1 {
		pageID := g.frame.pageID
		frameID := g.bpm.pageTable[pageID]
		g.bpm.arcReplacer.SetEvictable(frameID, pageID, true)
	}

	g.bpm = nil
	g.frame = nil
}

// BufferPoolManager 缓冲池管理器
type BufferPoolManager struct {
	mu            sync.Mutex
	poolSize      uint64
	frames        []*FrameHeader
	pageTable     map[PageID]FrameID
	arcReplacer   *ArcReplacer
	diskScheduler *DiskScheduler
	nextPageID    atomic.Uint64
	pageSize      uint64
}

// NewBufferPoolManager 创建缓冲池管理器
func NewBufferPoolManager(poolSize, pageSize uint64, diskScheduler *DiskScheduler) *BufferPoolManager {
	frames := make([]*FrameHeader, poolSize)
	for i := range frames {
		frames[i] = &FrameHeader{
			data: make([]byte, pageSize),
		}
	}

	return &BufferPoolManager{
		poolSize:      poolSize,
		frames:        frames,
		pageTable:     make(map[PageID]FrameID),
		arcReplacer:   NewArcReplacer(poolSize),
		diskScheduler: diskScheduler,
		pageSize:      pageSize,
	}
}

// NewPage 创建新页
func (b *BufferPoolManager) NewPage() (PageID, error) {
	b.mu.Lock()
	defer b.mu.Unlock()

	newPageID := PageID(b.nextPageID.Add(1))
	frameID, ok := b.findFreeFrame()
	if !ok {
		return 0, ErrNoFreeFrame
	}

	frame := b.frames[frameID]
	frame.pageID = newPageID
	frame.isDirty = false
	frame.pinCount.Store(1)

	b.pageTable[newPageID] = frameID
	b.arcReplacer.SetEvictable(frameID, newPageID, false)

	// 记录新页的访问
	b.arcReplacer.RecordAccess(frameID, newPageID)

	return newPageID, nil
}

// CheckedReadPage 读取页
func (b *BufferPoolManager) CheckedReadPage(pageID PageID) (*ReadPageGuard, error) {
	b.mu.Lock()
	defer b.mu.Unlock()

	// 检查页是否在内存中
	if frameID, ok := b.pageTable[pageID]; ok {
		frame := b.frames[frameID]
		frame.pinCount.Add(1)
		b.arcReplacer.SetEvictable(frameID, pageID, false)
		b.arcReplacer.RecordAccess(frameID, pageID)
		return &ReadPageGuard{bpm: b, frame: frame}, nil
	}

	// 页不在内存，查找空闲帧
	frameID, ok := b.findFreeFrame()
	if !ok {
		return nil, ErrNoFreeFrame
	}
	frame := b.frames[frameID]

	// 从磁盘读取
	req := &DiskRequest{
		IsWrite: false,
		PageID:  pageID,
		Data:    frame.data,
	}
	if err := b.diskScheduler.Schedule(req); err != nil {
		return nil, err
	}
	<-req.Done

	// 初始化帧
	frame.pageID = pageID
	frame.isDirty = false
	frame.pinCount.Store(1)

	b.pageTable[pageID] = frameID
	b.arcReplacer.SetEvictable(frameID, pageID, false)

	return &ReadPageGuard{bpm: b, frame: frame}, nil
}

// CheckedWritePage 写入页
func (b *BufferPoolManager) CheckedWritePage(pageID PageID) (*WritePageGuard, error) {
	b.mu.Lock()
	defer b.mu.Unlock()

	// 检查页是否在内存中
	if frameID, ok := b.pageTable[pageID]; ok {
		frame := b.frames[frameID]
		frame.pinCount.Add(1)
		b.arcReplacer.SetEvictable(frameID, pageID, false)
		b.arcReplacer.RecordAccess(frameID, pageID)
		// 标记为脏页
		frame.isDirty = true
		return &WritePageGuard{bpm: b, frame: frame}, nil
	}

	// 页不在内存，查找空闲帧
	frameID, ok := b.findFreeFrame()
	if !ok {
		return nil, ErrNoFreeFrame
	}
	frame := b.frames[frameID]

	// 从磁盘读取
	req := &DiskRequest{
		IsWrite: false,
		PageID:  pageID,
		Data:    frame.data,
	}
	if err := b.diskScheduler.Schedule(req); err != nil {
		return nil, err
	}
	<-req.Done

	// 初始化帧
	frame.pageID = pageID
	frame.isDirty = true // 新创建的写页标记为脏页
	frame.pinCount.Store(1)

	b.pageTable[pageID] = frameID
	b.arcReplacer.SetEvictable(frameID, pageID, false)

	return &WritePageGuard{bpm: b, frame: frame}, nil
}

// FlushPage 将页写回磁盘
func (b *BufferPoolManager) FlushPage(pageID PageID) error {
	b.mu.Lock()
	defer b.mu.Unlock()
	return b.flushPageUnsafe(pageID)
}

// FlushAllPages 将所有脏页写回磁盘
func (b *BufferPoolManager) FlushAllPages() error {
	b.mu.Lock()
	defer b.mu.Unlock()

	for pageID := range b.pageTable {
		if err := b.flushPageUnsafe(pageID); err != nil {
			return err
		}
	}
	return nil
}

// Close 关闭缓冲池
func (b *BufferPoolManager) Close() error {
	if err := b.FlushAllPages(); err != nil {
		return err
	}
	b.diskScheduler.Stop()
	return nil
}

// 辅助方法：查找空闲帧
func (b *BufferPoolManager) findFreeFrame() (FrameID, bool) {
	// 查找未使用的帧
	for i := range b.frames {
		frame := b.frames[i]
		if frame.pinCount.Load() == 0 && frame.pageID == 0 {
			return FrameID(i), true
		}
	}

	// 驱逐一个可驱逐帧
	victimFrameID := b.arcReplacer.Evict()
	if victimFrameID == nil {
		return 0, false
	}

	// 处理被驱逐的帧
	frameID := *victimFrameID
	frame := b.frames[frameID]
	if frame.isDirty {
		if err := b.flushPageUnsafe(frame.pageID); err != nil {
			return 0, false
		}
	}

	// 重置帧
	oldPageID := frame.pageID
	delete(b.pageTable, oldPageID)
	frame.pageID = 0
	frame.isDirty = false
	frame.pinCount.Store(0)

	return frameID, true
}

// 辅助方法：无锁版本的FlushPage
func (b *BufferPoolManager) flushPageUnsafe(pageID PageID) error {
	frameID, ok := b.pageTable[pageID]
	if !ok {
		return ErrPageNotInPool
	}
	frame := b.frames[frameID]

	if !frame.isDirty {
		return nil
	}

	// 写回磁盘
	req := &DiskRequest{
		IsWrite: true,
		PageID:  pageID,
		Data:    frame.data,
	}
	if err := b.diskScheduler.Schedule(req); err != nil {
		return err
	}
	<-req.Done

	frame.isDirty = false
	return nil
}

// 用于测试的辅助方法：获取当前Pin计数
func (b *BufferPoolManager) GetPinCount(pageID PageID) uint32 {
	b.mu.Lock()
	defer b.mu.Unlock()

	frameID, ok := b.pageTable[pageID]
	if !ok {
		return 0
	}
	return b.frames[frameID].pinCount.Load()
}

// 用于测试的辅助方法：获取MRU目标大小
func (a *ArcReplacer) GetMRUTargetSize() uint64 {
	a.mu.Lock()
	defer a.mu.Unlock()
	return a.mruTargetSize
}

// 用于测试的辅助方法：检查帧是否在MFU列表
func (a *ArcReplacer) IsInMFU(frameID FrameID) bool {
	a.mu.Lock()
	defer a.mu.Unlock()

	listType, ok := a.frameListType[frameID]
	return ok && listType == a.mfu
}

// --------------------------- 测试代码 ---------------------------

func main() {
	// 简单测试
	pageSize := uint64(8192)
	poolSize := uint64(3)

	// 创建磁盘管理器和调度器
	diskManager := &MockDiskManager{}
	diskScheduler := NewDiskScheduler(diskManager)
	diskScheduler.Start()
	defer diskScheduler.Stop()

	// 创建缓冲池管理器
	bpm := NewBufferPoolManager(poolSize, pageSize, diskScheduler)
	defer func() {
		if err := bpm.Close(); err != nil {
			fmt.Printf("关闭缓冲池失败: %v\n", err)
		}
	}()

	// 测试创建新页
	page1, err := bpm.NewPage()
	if err != nil {
		fmt.Printf("创建新页失败: %v\n", err)
		return
	}
	fmt.Printf("创建新页: %d\n", page1)

	// 测试写入页
	writeGuard, err := bpm.CheckedWritePage(page1)
	if err != nil {
		fmt.Printf("写入页失败: %v\n", err)
		return
	}

	// 写入数据
	data := writeGuard.Data()
	copy(data, []byte("测试数据: Buffer Pool Manager"))
	fmt.Println("写入数据完成")
	writeGuard.Close()

	// 测试读取页
	readGuard, err := bpm.CheckedReadPage(page1)
	if err != nil {
		fmt.Printf("读取页失败: %v\n", err)
		return
	}

	// 验证数据
	fmt.Printf("读取到的数据: %s\n", string(readGuard.Data()[:30]))
	readGuard.Close()

	// 测试页驱逐（创建超过缓冲池容量的页）
	for i := 0; i < 5; i++ {
		page, err := bpm.NewPage()
		if err != nil {
			fmt.Printf("创建第%d个页失败: %v\n", i+2, err)
			break
		}
		fmt.Printf("创建新页: %d\n", page)
	}

	fmt.Println("测试完成")
}
